package leetcode2;
import java.util.*;
public class Day13 {


    public static void main(String[] args) {
        String s  = "cbaebabacd";
        String p = "abc";
    }

    public boolean isValid(String s) {
        //思路：左括号进栈，右括号出栈一次进行比对

        Stack<Character> stack = new Stack<>();
        for(int i=0;i<s.length();i++) {
            char ch = s.charAt(i);
            if(ch == '(' || ch == '[' || ch == '{') {
                //进栈
                stack.push(ch);
            }else {
                //出栈,ch为右括号
                if(stack.isEmpty()) return false;
                char top = stack.pop();//左括号
                if(ch == ')') {
                    if(top != '(') return false;
                }else if(ch == ']') {
                    if(top != '[') return false;
                }else {
                    if(top != '{') return false;
                }
            }
        }
        return stack.isEmpty()?true:false;
    }

    public List<Integer> findAnagrams(String s, String p) {
        //遍历s，找出里面存在p的
        //1.如何判断两个字符串是否是字母异位词 -- 使用两个map判断是否相同
        List<Integer> ret = new ArrayList<>();
        int sl=s.length(),pl=p.length();
        int[] flag = new int[26]; //记录p
        for(int i=0;i<pl;i++) {
            flag[p.charAt(i)-97]++;
        }
        int[] target = new int[26]; //记录s
        for(int left=0,right=0;right<sl;right++) {
            //1.进窗口
            target[s.charAt(right)-97]++;
            //2.判断是否需要出窗口
            if(right-left+1>pl) { //窗口的长度 》 字符串p的长度
                target[s.charAt(left++)-97]--;
            }
            //3.判断当前窗口内的字符串是否为异位词
            if(right-left+1 == pl) {
                int bool = -1;
                for(int i=0;i<26;i++) {
                    if(flag[i]!=target[i]) {
                        bool = 1;
                        break;
                    }
                }
                if(bool == -1) { //满足异位词，记录结果
                    ret.add(left);
                }
            }
        }
        return ret;
    }


    //119.杨辉三角
    public List<Integer> getRow(int rowIndex) {
        List<Integer> ret = new ArrayList<>();
        int[][] nums = new int[rowIndex+1][rowIndex+1];

        for(int i=0;i<rowIndex+1;i++) {
            for(int j=0;j<=i;j++) {
                if(j==0 || i==j) nums[i][j]=1;
                else nums[i][j] = nums[i-1][j] + nums[i-1][j-1];
            }
        }
        for(int i=0;i<rowIndex+1;i++) {
            ret.add(nums[rowIndex][i]);
        }
        return ret;
    }






}
